{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Permutation I LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: permutation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #无重复字符串的排列组合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。</p>\n",
    "\n",
    "<p> <strong>示例1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong> 输入</strong>：S = \"qwe\"\n",
    "<strong> 输出</strong>：[\"qwe\", \"qew\", \"wqe\", \"weq\", \"ewq\", \"eqw\"]\n",
    "</pre>\n",
    "\n",
    "<p> <strong>示例2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong> 输入</strong>：S = \"ab\"\n",
    "<strong> 输出</strong>：[\"ab\", \"ba\"]\n",
    "</pre>\n",
    "\n",
    "<p> <strong>提示:</strong></p>\n",
    "\n",
    "<ol>\n",
    "<li>字符都是英文字母。</li>\n",
    "<li>字符串长度在[1, 9]之间。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [permutation-i-lcci](https://leetcode.cn/problems/permutation-i-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [permutation-i-lcci](https://leetcode.cn/problems/permutation-i-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = []\n",
    "        self.res = ''\n",
    "    def traceback(self, start, n, S, used):\n",
    "        if len(self.res) == n:\n",
    "            self.ans.append(self.res)\n",
    "            return\n",
    "        for i in range(n):\n",
    "            if used[i]:\n",
    "                continue\n",
    "            used[i] = True\n",
    "            self.res += S[i]\n",
    "            self.traceback(i+1, n, S, used)\n",
    "            self.res = self.res[:-1]\n",
    "            used[i] = False\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        # 排列问题, 对比组合问题，要多一个记录是否使用了元素的数组\n",
    "        n = len(S)\n",
    "        used = [0]*n\n",
    "        self.traceback(0, n, S, used)\n",
    "        return self.ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        res_list = []\n",
    "        self.bt(S, \"\", len(S), res_list)\n",
    "        return res_list\n",
    "    \n",
    "    def bt(self, S, res, total_len, res_list):\n",
    "        if len(S) == 1:\n",
    "            res = res + S\n",
    "            if len(res) == total_len:\n",
    "                res_list.append(res)\n",
    "        for i, ele in enumerate(S):\n",
    "            S = S.replace(ele, \"\", 1)\n",
    "            self.bt(S, res + ele, total_len, res_list)\n",
    "            S = S[:i] + ele + S[i:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        length = len(S)\n",
    "        lists = []\n",
    "        for i in permutations(S,length):\n",
    "            lists.append(\"\".join(i))\n",
    "        return lists\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        tag = [False for _ in range(len(S))]\n",
    "        def dfs():\n",
    "            res = []\n",
    "            for i in range(len(S)):\n",
    "                if not tag[i]:\n",
    "                    tag[i] = True\n",
    "                    tmp = dfs()\n",
    "                    tag[i] = False\n",
    "                    for t in tmp:\n",
    "                        res.append(S[i] + t)\n",
    "            return res if len(res) > 0 else ['']\n",
    "        return dfs()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        from itertools import permutations\n",
    "        result = []\n",
    "        for i in permutations(S, len(S)):\n",
    "            result.append(\"\".join(i))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if S == \"\":\n",
    "            return []\n",
    "        ans = []\n",
    "        self.dfs(S, \"\", ans)\n",
    "        return ans\n",
    "\n",
    "    def dfs(self, s: str, total: str, ans):\n",
    "        if len(s) == 1:\n",
    "            ans.append(total+s)\n",
    "            return ans\n",
    "        for i in range(len(s)):\n",
    "            self.dfs(s[:i] + s[i+1:], total + s[i], ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        def helper(res,left,right):\n",
    "            if len(right)==0:\n",
    "                res.append(left)\n",
    "            for i in range(len(right)):\n",
    "                helper(res,left+right[i],right[:i]+right[i+1:])\n",
    "            return res\n",
    "        return helper([],\"\",S)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import permutations\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        return [\"\".join(i) for i in permutations(S, r=len(S))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import permutations\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        ans = list()\n",
    "        for i in permutations(S,len(S)):\n",
    "            ans.append(\"\".join(i))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        n = len(S)\n",
    "        return self.permute([c for c in S], n, [False] * n, \"\")\n",
    "\n",
    "    def permute(\n",
    "        self,\n",
    "        chs: List[str],\n",
    "        num_left: int,\n",
    "        used: List[bool],\n",
    "        permutation: str,\n",
    "    ) -> List[str]:\n",
    "        permutations = []\n",
    "        for i in range(len(chs)):\n",
    "            if used[i]:\n",
    "                continue\n",
    "            used[i] = True\n",
    "            num_left -= 1\n",
    "            if num_left == 0:\n",
    "                permutations.append(permutation + chs[i])\n",
    "            else:\n",
    "                permutations += self.permute(\n",
    "                    chs,\n",
    "                    num_left,\n",
    "                    used,\n",
    "                    permutation + chs[i],\n",
    "                )\n",
    "            used[i] = False\n",
    "            num_left += 1\n",
    "        return permutations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        import itertools\n",
    "        l = []\n",
    "        for i in itertools.permutations(S,len(S)):\n",
    "            l.append(''.join(i))\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        l = [S[0]]\n",
    "        for i in range(1,len(S)):\n",
    "            s = S[i]\n",
    "            l_len = len(l)\n",
    "            for j in range(l_len):\n",
    "                temp = l.pop(0)\n",
    "                for x in range(len(temp)+1):\n",
    "                    l.append(temp[:x]+s+temp[x:])\n",
    "        return l\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        ans = []\n",
    "\n",
    "        def backtrack(s, remainder):\n",
    "            m = len(remainder)\n",
    "            if m == 1:\n",
    "                s.append(remainder)\n",
    "                ans.append(''.join(s))\n",
    "                s.pop()\n",
    "                return\n",
    "            for i in range(m):\n",
    "                s.append(remainder[i])\n",
    "                backtrack(s, remainder[:i] + remainder[i + 1:])\n",
    "                s.pop()\n",
    "\n",
    "        backtrack([], S)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, s: str) -> List[str]:\n",
    "        return [ ''.join(item) for item in permutations(list(s))]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        self.char_arr = []\n",
    "        self.n = len(S)\n",
    "        for i in range(self.n):\n",
    "            self.char_arr.append(S[i])\n",
    "        self.ans = []\n",
    "        self.backtrack(0)\n",
    "        return self.ans\n",
    "\n",
    "    def backtrack(self, pos: int):\n",
    "        if pos == self.n:\n",
    "            self.ans.append(''.join(self.char_arr))\n",
    "            return\n",
    "        for i in range(pos + 1):\n",
    "            temp = self.char_arr[i]\n",
    "            self.char_arr[i] = self.char_arr[pos] \n",
    "            self.char_arr[pos] = temp\n",
    "            self.backtrack(pos + 1)\n",
    "            self.char_arr[pos] = self.char_arr[i]\n",
    "            self.char_arr[i] = temp\n",
    "         \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if S == \"\":\n",
    "            return []\n",
    "        path = []\n",
    "        def back(cur,shem):\n",
    "            if shem == \"\":\n",
    "                path.append(\"\".join(cur))\n",
    "            else:\n",
    "                for i,j in enumerate(shem):\n",
    "                    cur.append(j)\n",
    "                    back(cur,shem[:i]+shem[i+1:])\n",
    "                    cur.pop()\n",
    "        back([],S)\n",
    "        return path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        dic = {}\n",
    "        res = []\n",
    "        n = len(S)\n",
    "        def iter(sub):\n",
    "            if len(sub) == n:\n",
    "                res.append(sub)\n",
    "                return\n",
    "            for s in S:\n",
    "                if s in dic:\n",
    "                    continue\n",
    "                dic[s] = 1\n",
    "                iter(sub + s)\n",
    "                del dic[s]\n",
    "        iter('')\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if S == \"\":\n",
    "            return []\n",
    "        \n",
    "        res = []\n",
    "        path = ''\n",
    "\n",
    "        def backtrack(S, path, res):\n",
    "            if S == \"\":\n",
    "                res.append(path)\n",
    "                return \n",
    "            \n",
    "            for i in range(len(S)):\n",
    "                cur = S[i]\n",
    "                backtrack(S[:i] + S[i+1:], path + cur, res)\n",
    "        \n",
    "        backtrack(S, path, res)\n",
    "\n",
    "        return res   \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        res=[]\n",
    "        S=list(S)\n",
    "        def dfs(S,start,end):\n",
    "            if start==end:\n",
    "                s=\"\".join(S)\n",
    "                res.append(s)\n",
    "                return \n",
    "            for i in range(start,end+1):\n",
    "                S[i],S[start]=S[start],S[i]\n",
    "                dfs(S,start+1,end)\n",
    "                S[i],S[start]=S[start],S[i]\n",
    "        dfs(S,0,len(S)-1)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        res = []\n",
    "        path = []\n",
    "\n",
    "        list_S = list(S)\n",
    "        used = [False for i in range(len(list_S))]\n",
    "\n",
    "        def backtrack():\n",
    "            if len(path) == len(S):\n",
    "                res.append(''.join(path[:]))\n",
    "                return\n",
    "            if len(path) > len(S):\n",
    "                return\n",
    "            \n",
    "            for i in range(len(S)):\n",
    "                if used[i] == False:\n",
    "                    used[i] = True\n",
    "                    path.append(list_S[i])\n",
    "                    backtrack()\n",
    "                    path.pop()\n",
    "                    used[i] = False\n",
    "        backtrack()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        # def dfs(level, n, s):\n",
    "        #     if level == n:\n",
    "        #         ans.append(s)\n",
    "        #         return\n",
    "        #     for i in range(n):\n",
    "        #         if S[i] in s:\n",
    "        #             continue\n",
    "        #         dfs(level+1, n, s+S[i])\n",
    "        \n",
    "        def dfs(S, n, path):\n",
    "            if len(path) == n:\n",
    "                ans.append(path)\n",
    "                return\n",
    "            for i in range(len(S)):\n",
    "                dfs(S[:i]+S[i+1:], n, path+S[i])\n",
    "        \n",
    "        ans = []\n",
    "        dfs(S,len(S),\"\")\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        len_s = len(S)\n",
    "\n",
    "        self.path = []\n",
    "        self.res = []\n",
    "        self.used = [False]*len_s\n",
    "\n",
    "\n",
    "        def dfs():\n",
    "            if len(self.path) == len(S):\n",
    "                self.res.append(''.join(self.path[:]))\n",
    "\n",
    "            \n",
    "            for i in range(len_s):\n",
    "                if not self.used[i]:\n",
    "                    self.used[i] = True\n",
    "                    self.path.append(S[i])\n",
    "                    dfs()\n",
    "                    self.path.pop()\n",
    "                    self.used[i] = False\n",
    "\n",
    "        \n",
    "\n",
    "        dfs()\n",
    "\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recursion(self,res,S,temp):\n",
    "        if S=='':\n",
    "          res.append(temp)\n",
    "        else:\n",
    "          for i in range(len(S)):\n",
    "            cur = S[i]\n",
    "            self.recursion(res,S[:i]+S[i+1:],temp+cur)\n",
    "\n",
    "\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        res=[]\n",
    "        temp =''\n",
    "        self.recursion(res,S,temp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if len(S)==0:\n",
    "            return []\n",
    "        ans = []\n",
    "        def back(letters,res):\n",
    "            if len(res)==0:\n",
    "                ans.append(''.join(letters))\n",
    "                return \n",
    "            else:\n",
    "                for i in range(len(res)):\n",
    "                    letters.append(res[i])\n",
    "                    back(letters,res[:i]+res[i+1:])\n",
    "                    letters.pop()\n",
    "\n",
    "        back([],list(S))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        sl = []\n",
    "        for e in itertools.permutations(S):\n",
    "            a = \"\".join(e)\n",
    "            sl.append(a)\n",
    "        sl.sort()\n",
    "        return sl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recursion(self,res,S,index):\n",
    "        s=list(S)\n",
    "        if index == len(s)-1:\n",
    "            res.append(''.join(s))\n",
    "        else:\n",
    "            for i in range(index,len(s)):\n",
    "                s[i],s[index] = s[index],s[i]\n",
    "                self.recursion(res,s,index+1)\n",
    "                s[i],s[index]=s[index],s[i]\n",
    "\n",
    "\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        res=[]\n",
    "        self.recursion(res,S,0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        \n",
    "        if S == \"\":\n",
    "            return []\n",
    "        if len(S) == 1:\n",
    "            return [S]\n",
    "        res = []\n",
    "        placeholder = S[0]\n",
    "        others = self.permutation(S[1:])\n",
    "        for other in others:\n",
    "            for i in range(len(other)+1):\n",
    "                tmp = other[:i] + placeholder + other[i:]\n",
    "                res.append(tmp)\n",
    "        return res\n",
    "        # if len(S) == 1:\n",
    "        #     return [S]\n",
    "        # else:\n",
    "        #     ans = []\n",
    "        #     for x  in self.permutation(S[1:]):\n",
    "        #         ans += [(x[:i] + S[0] + x[i:]) for i in range(len(x)+1)]\n",
    "        #     return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        \n",
    "        # if S == \"\":\n",
    "        #     return []\n",
    "        # if len(S) == 1:\n",
    "        #     return [S]\n",
    "        # res = []\n",
    "        # placeholder = S[0]\n",
    "        # others = self.permutation(S[1:])\n",
    "        # for other in others:\n",
    "        #     for i in range(len(other)+1):\n",
    "        #         tmp = other[:i] + placeholder + other[i:]\n",
    "        #         if tmp not in res:\n",
    "        #             res.append(tmp)\n",
    "        # return res\n",
    "        if len(S) == 1:\n",
    "            return [S]\n",
    "        else:\n",
    "            ans = []\n",
    "            for x  in self.permutation(S[1:]):\n",
    "                ans += [(x[:i] + S[0] + x[i:]) for i in range(len(x)+1)]\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, string: str) -> List[str]:\n",
    "        # 选中第一个字符\n",
    "        res = [string[0]]\n",
    "        # 选中第一个字符后面的每个字符\n",
    "        for char in string[1:]:\n",
    "            # 当前正在构建的字符串集\n",
    "            cur = []\n",
    "            # 遍历之前得到的每组结果\n",
    "            for group in res:\n",
    "                # 每组结果的每个位置，都尝试插入 char\n",
    "                for i in range(len(group) + 1):\n",
    "                    # 插入后得到新的字符串，随后得到一个新的结果\n",
    "                    cur.append(group[:i] + char + group[i:])\n",
    "            # 更新结果集\n",
    "            res = cur\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        return list([''.join(path) for path in itertools.permutations(S, len(S))])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if len(S) == 1:\n",
    "            return [S]\n",
    "        ans = []\n",
    "        for subS in self.permutation(S[1:]):\n",
    "            for i in range(len(subS)+1):\n",
    "                ans.append(subS[:i]+ S[0:1]+ subS[i:])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if len(S)==1:\n",
    "            return [S]\n",
    "        else:\n",
    "            ans = []\n",
    "            for x in self.permutation(S[1:]):\n",
    "                ans += [(x[:i] + S[0] + x[i:]) for i in range(len(x)+1)]\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        def dfs(S,epoch):\n",
    "            if len(epoch) == len(S):\n",
    "                ans.append(epoch)\n",
    "                return\n",
    "            \n",
    "            for i in range(len(S)):\n",
    "                if label[i]: continue\n",
    "                label[i] = True\n",
    "                epoch += S[i]\n",
    "                dfs(S,epoch)\n",
    "                epoch = epoch[:-1]\n",
    "                label[i] = False\n",
    "\n",
    "        ans = []\n",
    "        label = [False] * len(S)\n",
    "        dfs(S,\"\")\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        def dfs(S,epoch):\n",
    "            if len(epoch) == len(S):\n",
    "                ans.append(\"\".join(epoch))\n",
    "                return\n",
    "            \n",
    "            for i in range(len(S)):\n",
    "                if label[i]: continue\n",
    "                label[i] = True\n",
    "                epoch.append(S[i])\n",
    "                dfs(S,epoch)\n",
    "                epoch.pop()\n",
    "                label[i] = False\n",
    "        ans = []\n",
    "        epoch = []\n",
    "        label = [False] * len(S)\n",
    "        dfs(S,epoch)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        #copy\n",
    "        if S == '':\n",
    "            return []\n",
    "        res = []\n",
    "        path = ''\n",
    "        def backtrack(S,path,res):\n",
    "            if S =='':\n",
    "                res.append(path)\n",
    "                return\n",
    "            for i in range(len(S)):\n",
    "                cur = S[i]\n",
    "                backtrack(S[:i]+S[i+1:],path+cur,res)\n",
    "        \n",
    "        backtrack(S,path,res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def switch(self, string: str, index1, index2):\n",
    "        s_ls = [c for c in string]\n",
    "        # print(s_ls)\n",
    "        a = s_ls[index1]\n",
    "        s_ls[index1] = s_ls[index2]\n",
    "        s_ls[index2] = a\n",
    "        # print(s_ls)\n",
    "        return ''.join(s_ls)\n",
    "\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        \"\"\"\n",
    "        思路：1. 字符串第一个位置，可以需要遍历字符串内的所有字符，生成对应的新字符串\n",
    "             2. 第二个位置，需要遍历所有字符串内的除了第一个位置的字符，生成对应的新字符串\n",
    "             3. 第n个位置，需要便利除了之前n个字符的其他字符，每个都生成新的字符穿。\n",
    "        在实际操作中，难点主要在于如何确定剩余字符的内容，以及如何遍历，可使用互换位置的方式实现：\n",
    "            例如，对于第一个位置，只需要原始字符串的第一个位置与后续的字母进行位置互换，其所生产的字符串集合，\n",
    "            就相当于第一个字母已经是遍历过所有字符生成的。第一个位置的已经确定，现在来确定第二个位置。\n",
    "            而在第2个位置，对于已经生成的每个字符，把该位置的字符与其后面的字符互换，其生成的新的字符串的集合，即是上述第2点\n",
    "            因为从第2个位置开始，和后面的呼唤互换，就相当于遍历除掉第一个位置之外的元素。\n",
    "            重复以上步骤，直到第n个位置完成，所得字符串列表即所求。\n",
    "        \"\"\"\n",
    "\n",
    "        ls = [S]\n",
    "        ls_new = []     \n",
    "\n",
    "        # print(self.switch('abc', 1, 2))\n",
    "\n",
    "        # 从第0个位置开始遍历\n",
    "        for i in range(len(S)):\n",
    "            # 针对每一个位置，每一个已有的字符穿都要进行交换\n",
    "            for s in ls:\n",
    "                # 从i的下一位开始，分别与后面的字符互换，形成新的字符串，并收集\n",
    "                for j in range(i+1, len(S)):\n",
    "                    word = self.switch(s, i, j)\n",
    "                    ls_new.append(word)         # 注意这里不能在里面添加，不然会死循环\n",
    "                    # print(i, j, s, ls_new)\n",
    "            ls = ls+ls_new                      # 互换完成后，把新的字符串添加到已有字符串中\n",
    "            ls_new = []                         # 新字符串重置\n",
    "            # print(ls)\n",
    "        return ls\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "\"qwe\"\n",
    "\"ab\"\n",
    "\n",
    "All charaters are English letters.\n",
    "1 <= S.length <= 9\n",
    "\n",
    "String, Backtracking\n",
    "\"\"\"\n",
    "\n",
    "def swap(arr, i, j):\n",
    "    tmp = arr[i]\n",
    "    arr[i] = arr[j]\n",
    "    arr[j] = tmp\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        res = []\n",
    "        self.dfs(list(S), 0, res)\n",
    "        return res\n",
    "    def dfs(self, charArr, k, res):\n",
    "        if k == len(charArr):\n",
    "            res.append(''.join(charArr))\n",
    "            return\n",
    "        for i in range(k, len(charArr)):\n",
    "            swap(charArr, i, k)\n",
    "            self.dfs(charArr, k+1, res)\n",
    "            swap(charArr, i, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        ans=[]\n",
    "        for x in permutations(S,len(S)):\n",
    "            ans.append(\"\".join(x))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        ret = []\n",
    "        self.recursive(S,[],ret)\n",
    "        return ret \n",
    "    def recursive(self, S, path, ret):\n",
    "        if not S:\n",
    "            ret.append(''.join(path))\n",
    "            return \n",
    "        for i in range(len(S)):\n",
    "            self.recursive(S[:i]+S[i+1:], path + [S[i]], ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if S == '':return []\n",
    "        res = []\n",
    "        path = ''\n",
    "        def backtrack(S, path, res):\n",
    "            if S == '':\n",
    "                res.append(path)\n",
    "                return \n",
    "\n",
    "            for i in range(len(S)):\n",
    "                cur = S[i]\n",
    "                backtrack(S[:i] + S[i+1:], path + cur, res)\n",
    "                \n",
    "        backtrack(S, path, res)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        def fun(path,res,uesd):\n",
    "            if len(path) == len(S):\n",
    "                res.append(\"\".join(path[:]))\n",
    "                return\n",
    "            for i in range(len(S)):\n",
    "                if uesd[i]:\n",
    "                    continue\n",
    "                used[i] = True\n",
    "                path.append(S[i])\n",
    "                fun(path,res,used)\n",
    "                path.pop()\n",
    "                used[i] = False\n",
    "        used = [False]*len(S)\n",
    "        res = []\n",
    "        fun([],res,used)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if S=='':return []\n",
    "        res=[]\n",
    "        path=[]\n",
    "        def backtrack(S,path,res):\n",
    "            if S==\"\":\n",
    "                res.append(\"\".join(path))\n",
    "                return\n",
    "            for i in range(len(S)):\n",
    "                #cur=S[i]\n",
    "                path.append(S[i])\n",
    "                #backtrack(S[:i]+S[i+1:],path+cur,res)\n",
    "                backtrack(S[:i]+S[i+1:],path,res)\n",
    "                path.pop()\n",
    "        \n",
    "        backtrack(S,path,res)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if S == '':return []\n",
    "        res = []\n",
    "        path = ''\n",
    "        def backtrack(S, path, res):\n",
    "            if S == '':\n",
    "                res.append(path)\n",
    "                return \n",
    "\n",
    "            for i in range(len(S)):\n",
    "                cur = S[i]\n",
    "                backtrack(S[:i] + S[i+1:], path + cur, res)\n",
    "                \n",
    "        backtrack(S, path, res)\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recursion(self,res,S,index):\n",
    "        s=list(S)\n",
    "        if index == len(s)-1:\n",
    "            res.append(''.join(s))\n",
    "        else:\n",
    "            for i in range(index,len(s)):\n",
    "                s[i],s[index] = s[index],s[i]\n",
    "                self.recursion(res,s,index+1)\n",
    "                s[i],s[index]=s[index],s[i]\n",
    "\n",
    "\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        res=[]\n",
    "        self.recursion(res,S,0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if S == '':return []\n",
    "        res = []\n",
    "        path = ''\n",
    "        def backtrack(S, path, res):\n",
    "            if S == '':\n",
    "                res.append(path)\n",
    "                return \n",
    "\n",
    "            for i in range(len(S)):\n",
    "                cur = S[i]\n",
    "                backtrack(S[:i] + S[i+1:], path + cur, res)\n",
    "                \n",
    "        backtrack(S, path, res)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if S == '':return []\n",
    "        res = []\n",
    "        path = ''\n",
    "        def backtrack(S, path, res):\n",
    "            if S == '':\n",
    "                res.append(path)\n",
    "                return \n",
    "\n",
    "            for i in range(len(S)):\n",
    "                cur = S[i]\n",
    "                backtrack(S[:i] + S[i+1:], path + cur, res)\n",
    "                \n",
    "        backtrack(S, path, res)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if S == '':return []\n",
    "        res = []\n",
    "        path = ''\n",
    "        def backtrack(S, path, res):\n",
    "            if S == '':\n",
    "                res.append(path)\n",
    "                return \n",
    "\n",
    "            for i in range(len(S)):\n",
    "                cur = S[i]\n",
    "                backtrack(S[:i] + S[i+1:], path + cur, res)\n",
    "                \n",
    "        backtrack(S, path, res)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "\n",
    "        def dfs(S, path, res ):\n",
    "            if S == '':\n",
    "                res.append(path)\n",
    "                return\n",
    "            for i in range( len(S)):\n",
    "                cur = S[i]\n",
    "                dfs(S[:i] + S[i+1:], path + cur, res)\n",
    "        \n",
    "\n",
    "        res = []\n",
    "        path = ''\n",
    "        if S=='': return []\n",
    "        dfs(S, path, res)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        res = [\"\"]\n",
    "        for i in range(len(S)):\n",
    "            res1 = []\n",
    "            for j in range(len(res)):\n",
    "                for k in range(i+1):\n",
    "                    res1.append(res[j][:k]+S[i]+res[j][k:])\n",
    "            res = res1.copy()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if len(S)==1:\n",
    "            return [S]\n",
    "        ans=[]\n",
    "        for i in range(len(S)):\n",
    "            temp=S[:i]+S[i+1:]\n",
    "            ret=self.permutation(temp)\n",
    "            for t in ret:\n",
    "                ans.append(S[i]+t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        ans = list()\n",
    "        for i, c in enumerate(S):\n",
    "            rears = self.permutation(S[:i] + S[i+1:])\n",
    "            if len(rears) == 0:\n",
    "                ans.append(c)\n",
    "            else:\n",
    "                for rear in rears:\n",
    "                    ans.append(c + rear)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if len(S)==1:return [S]\n",
    "        ans=[]\n",
    "        for i in range(len(S)):\n",
    "            s=S[:i]+S[i+1:]\n",
    "            for string in self.permutation(s):ans.append(S[i]+string)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        ans=[]\n",
    "        def dfs(s,path):\n",
    "            nonlocal ans\n",
    "            if not s:\n",
    "                ans.append(path)\n",
    "                return\n",
    "            for i,c in enumerate(s):\n",
    "                dfs(s[:i]+s[i+1:],path+c)\n",
    "        dfs(S,'')\n",
    "        return ans\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, s: str) -> list[str]:\n",
    "        if len(s) == 1:\n",
    "            return [s]\n",
    "\n",
    "        p = []\n",
    "        for i in range(len(s)):\n",
    "            first_char = s[i]\n",
    "            rest_of_chars = s[:i] + s[i+1:]\n",
    "            for perm in self.permutation(rest_of_chars):\n",
    "                p.append(first_char + perm)\n",
    "\n",
    "        return p\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        counter = collections.Counter(S)\n",
    "        def find(counter, dic, prev):\n",
    "            end = True\n",
    "            for k,v in counter.items():\n",
    "                if v > 0:\n",
    "                    end = False\n",
    "                    c = counter.copy()\n",
    "                    c[k] -=1\n",
    "                    find(c, dic, prev+k)\n",
    "            if end:\n",
    "                dic[prev] = None\n",
    "        dic = {}\n",
    "        for k in counter.keys():\n",
    "            find(counter, dic, \"\")\n",
    "        return list(dic.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if len(S) == 0:\n",
    "            return  [\"\"]\n",
    "        res = []\n",
    "        for i in range(len(S)):\n",
    "            for j in self.permutation(S[:i]+S[i+1:]):\n",
    "                res.append(S[i] + j)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if len(S) == 0:\n",
    "            return []\n",
    "        result = []\n",
    "        \n",
    "        def back(cur,res):\n",
    "            if len(res) == 0:\n",
    "                result.append(''.join(cur))\n",
    "                return\n",
    "            for idx,char in enumerate(res):\n",
    "                cur.append(char)\n",
    "                back(cur,res[:idx]+res[idx+1:])\n",
    "                cur.pop()\n",
    "        back([],list(S))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        \n",
    "        res = []\n",
    "        path = ''\n",
    "      \n",
    "        def backtrack(S, path):\n",
    "            if S == '':\n",
    "                res.append(path)\n",
    "              \n",
    "                return \n",
    "\n",
    "            for i in range(len(S)):\n",
    "                cur = S[i]\n",
    "                backtrack(S[:i] + S[i+1:], path + cur)\n",
    "                \n",
    "        backtrack(S, path)\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if not S:\n",
    "            return []\n",
    "\n",
    "        def backtrack(signed, path, stemp):\n",
    "            if stemp == len(S):\n",
    "                res.append(''.join(path))\n",
    "            for i in range(len(S)):\n",
    "                if not signed[i]:\n",
    "                    path.append(S[i])\n",
    "                    signed[i] = True\n",
    "                    backtrack(signed, path, stemp+1)\n",
    "                    signed[i] = False\n",
    "                    path.pop()\n",
    "\n",
    "        res = []\n",
    "        backtrack([False for _ in range(len(S))], [], 0)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        length = len(S)\n",
    "        tag = [0] * length\n",
    "        res = []\n",
    "\n",
    "        def backtrack(single_res):\n",
    "            if len(single_res) == length:\n",
    "                res.append(''.join(single_res))\n",
    "                return\n",
    "\n",
    "            for i, single_char in enumerate(S):\n",
    "                if tag[i] == 1:\n",
    "                    continue\n",
    "                tag[i] = 1\n",
    "                single_res.append(single_char)\n",
    "                backtrack(single_res)\n",
    "                tag[i] = 0\n",
    "                single_res.pop()\n",
    "        backtrack([])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        outlist=[]\n",
    "        def mypermutation(S,nowstr):\n",
    "            if len(S)==0:\n",
    "                outlist.append(\"\".join(nowstr))\n",
    "            for index,item in enumerate(S):\n",
    "                nowstr.append(item)\n",
    "                mypermutation(S[:index]+S[index+1:],nowstr)\n",
    "                nowstr.pop()\n",
    "\n",
    "        mypermutation(S,[])\n",
    "        return outlist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        def dfs(s):\n",
    "            if s==\"\":\n",
    "                res.append(\"\".join(path))\n",
    "            for i in range(len(s)):\n",
    "                path.append(s[i])\n",
    "                dfs(s[:i]+s[i+1:])\n",
    "                path.pop()\n",
    "        path=[]\n",
    "        res=[]\n",
    "        dfs(S)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        n = len(S)\n",
    "        used = [False] * n\n",
    "\n",
    "        ans, path = [], []\n",
    "        def dfs():\n",
    "            nonlocal path\n",
    "            if len(path) == n:\n",
    "                ans.append(\"\".join(path[:]))\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if used[i]:\n",
    "                    continue\n",
    "                used[i] = True\n",
    "                path.append(S[i])\n",
    "                dfs()\n",
    "                used[i] = False\n",
    "                path.pop()\n",
    "        dfs()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if S == '':return []\n",
    "        res = []\n",
    "        path = ''\n",
    "        def backtrack(S, path):\n",
    "            if S == '':\n",
    "                res.append(path)\n",
    "                return \n",
    "            for i in range(len(S)):\n",
    "                cur = S[i]\n",
    "                backtrack(S[:i] + S[i+1:], path + cur)   \n",
    "        backtrack(S, path)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if len(S) == 0:\n",
    "            return []\n",
    "        result = []\n",
    "        path = ''\n",
    "        n = len(S)\n",
    "        def dfs(x,path):\n",
    "            if len(path) == n:\n",
    "                result.append(path)\n",
    "                return\n",
    "            for i in range(len(x)):\n",
    "                cur = x[i]\n",
    "                dfs(x[:i] + x[i+1:],path + cur)\n",
    "        \n",
    "        dfs(S,path)\n",
    "        return result\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "\n",
    "\n",
    "        res = []\n",
    "        n = len(S)\n",
    "        S = list(S)\n",
    "        def trackback(idx = 0):\n",
    "            if idx == n:\n",
    "                res.append(\"\".join(S))\n",
    "\n",
    "            for i in range(idx, n):\n",
    "\n",
    "                S[i], S[idx] = S[idx], S[i]\n",
    "                trackback(idx + 1)\n",
    "                S[i], S[idx] = S[idx], S[i]\n",
    "\n",
    "        trackback() \n",
    "\n",
    "        return res       \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        result = []\n",
    "        chars = [char for char in S]\n",
    "        def backtrack(path):\n",
    "            if len(path) == len(chars):\n",
    "                tmp = \"\"\n",
    "                for item in path:\n",
    "                    tmp += item\n",
    "                result.append(tmp)\n",
    "                return\n",
    "\n",
    "            for char in chars:\n",
    "                if char not in path:        \n",
    "                    path.append(char)\n",
    "                    backtrack(path)\n",
    "                    path.pop()\n",
    "\n",
    "        \n",
    "        backtrack([])\n",
    "        return result\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        result=[]\n",
    "        s=list(S)\n",
    "        def track(path,choices):\n",
    "            if len(path)==len(choices):\n",
    "                result.append(\"\".join(path))\n",
    "            else:\n",
    "                for i in choices:\n",
    "                    if i in path:\n",
    "                        continue\n",
    "                    else:\n",
    "                        path.append(i)\n",
    "                        track(path,choices)\n",
    "                        path.pop()\n",
    "        track([],s)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        # 递归过于明显了\n",
    "        def dfs(s,res,vis):\n",
    "            if len(res) == n:\n",
    "                ans.append(\"\".join(res))\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if vis[i]:\n",
    "                    continue\n",
    "                vis[i] = True\n",
    "                res.append(s[i])\n",
    "                dfs(s,res,vis)\n",
    "                res.pop()\n",
    "                vis[i] = False\n",
    "\n",
    "        ans = []\n",
    "        n = len(S)\n",
    "        visited = [False] * n\n",
    "        dfs(S,[],visited)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        res =[]\n",
    "        size =len(S)\n",
    "        def dfs(s,is_visited):\n",
    "            if len(s)==size:\n",
    "                res.append(s)\n",
    "                return \n",
    "            for i ,flag in enumerate(is_visited):\n",
    "                if not flag:\n",
    "                    is_visited[i] = True\n",
    "                    dfs(s+S[i],is_visited)\n",
    "                    is_visited[i] = False\n",
    "        is_visited = [False]*size\n",
    "        dfs('',is_visited)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if len(S) == 0:\n",
    "            return []\n",
    "        elif len(S) == 1:\n",
    "            return [S]\n",
    "        ans = []\n",
    "        for i in range(len(S)):\n",
    "            temp1 = self.permutation(S[:i] + S[i+1:])\n",
    "            for s1 in temp1:\n",
    "                ans.append(S[i] + s1)\n",
    "            # print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        res = []\n",
    "        def f(path, s):\n",
    "            if len(s) == 0:\n",
    "                res.append(path)\n",
    "            for i in range(len(s)):\n",
    "                f(path + s[i], s[:i] + s[i+1:])\n",
    "        f('', S)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        temp = ['' for _ in range(len(S))]\n",
    "        visit = [True]*len(S)\n",
    "        res = []\n",
    "        def dfs(z):\n",
    "            if z == len(S):\n",
    "                res.append(''.join(temp))\n",
    "            for i in range(len(S)):\n",
    "                if visit[i] == True:\n",
    "                    temp[z] = S[i]\n",
    "                    visit[i] = False\n",
    "                    dfs(z+1)\n",
    "                    visit[i] = True\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        dict1 = collections.defaultdict(int)\n",
    "        for s in S:\n",
    "            dict1[s] += 1\n",
    "        self.ans = []\n",
    "        def dfs(dict1, path, N):\n",
    "            if len(path) == N:\n",
    "                self.ans.append(''.join(path))\n",
    "                return\n",
    "            for key in dict1.keys():\n",
    "                if dict1[key] == 0:\n",
    "                    continue\n",
    "                dict1[key] -= 1\n",
    "                dfs(dict1, path + [key], N)\n",
    "                dict1[key] += 1\n",
    "        dfs(dict1, [], len(S))\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        if len(S) == 0:\n",
    "            return []\n",
    "        result = []\n",
    "\n",
    "        def back(cur, res):  # 第一个参数代表当前的组合，第二个参数代表待选的元素\n",
    "            if len(res) == 0:  # 回溯跳出的条件，如果没有元素可以选择了，则将cur组成字符串然后压入结果集\n",
    "                result.append(''.join(cur))\n",
    "                return\n",
    "            for idx, charater in enumerate(res):  # 如果res不为空\n",
    "                cur.append(charater)\n",
    "                back(cur, res[:idx] + res[idx + 1:])  # 回溯\n",
    "                cur.pop()\n",
    "\n",
    "        back([], list(S))\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permutation(self, S: str) -> List[str]:\n",
    "        n=len(S)\n",
    "        path=['']*n\n",
    "        ans=[]\n",
    "        def dfs(i,s):\n",
    "            if i==n:\n",
    "                ans.append(''.join(path.copy()))\n",
    "                return\n",
    "            for j in s:\n",
    "                path[i]=j\n",
    "                dfs(i+1,s-{j})\n",
    "        dfs(0,set(S))\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
